/********************************************
 *        Fonctions de Sous-Graphes         *
 *               sousgraphe.c               *
 *                                          *
 *     Grivolet Alenda Bourgeois Ciabaud    *
 ********************************************/
#include <stdlib.h>
#include <stdio.h>

#include "sousgraphe.h"
#include "triangulation.h"
#include "structures.h"
#include "LexBFS.h"

#include "tests.h"

/** 
 * @author Bourgeois Jean-Louis
 * Fonction qui teste si L'ensemble E
 * Represente un sous-graphe triangule de G
 * @param G	Le Graphe 
 * @param E	L'ensemble des sommets
 * @return 	1 si triangule 0 sinon
 */
int estSousGrapheTriangule( Graphe G, Ensemble E )
{
	int i, resultat;
	Graphe sousGraphe;
	Maillon *tmp;
	initGraphe( &sousGraphe );

	for( i=0; i<G.nbSommets; i++)
	{
		if( E[i] == 1 )
		{
			FOREACH(tmp, G.Sommets[i])
			{
				if( E[tmp->elt] == 1 )
					creerVoisin( &sousGraphe, i, tmp->elt );
			}
		}
	}

	sousGraphe.nbSommets = G.nbSommets;
	
	
	Numerotation* num =  LexBFS( sousGraphe );


	resultat = verifLexBFS( *num, sousGraphe );
	
	freeGraphe( sousGraphe );
	free(num->Numero);
	free(num->Sommet);
	free(num);

	return resultat;
}



/**
 * @author Bourgeois Jean-Louis
 * Cette Fonction genere la combinaison a partir
 * de la position k en placant nb zero
 * @param G	Le graphe de depart
 * @param E	Ensemble generer
 * @param k	Premier element modifiable
 * @param nb	Nombre de zero a place
 * @return	1 si on a trouve un triangule 0 sinon
 */
int combinaison(Graphe G, Ensemble *E, int k, int nb)
{
	int i;

	/* Si on a genere une combinaison */
	if(nb == 0)
	{
		/* On regarde si il est triangule */
		return estSousGrapheTriangule(G, *E);
	}
	else
	{
		/* On genere tout les combinaisons */
		for( i=k; i<G.nbSommets; i++)
		{
			/* Si l'element est modifiable */
			if( (*E)[i] == 1 )
			{
				/* On le modifie */
				(*E)[i] = 0;
				/* On genere Les combinaisons */
				if( combinaison(G, E, i, nb-1) )
					return 1;
				/* On le restore */
				(*E)[i] = 1;
			}
		}
	}
	
	return 0;
	
}



/**
 * @author Bourgeois Jean-Louis
 * Cette Fonction recherche le sous-graphe 
 * maximum triangule de G.
 * @param G	Le Graphe
 * @param E	L'ensemble des sommets qui reprensente se sous-graphe
 * @return	1 si il en trouve un et place l'ensemble dans E, 0 sinon
 */
int sousGrapheMaximum( Graphe G, Ensemble *E)
{
	int i;
	
	/* Creation dynamique de E */
	*E = calloc(G.nbSommets, sizeof(int) );
	
	/* Au debut on considere le graphe en entier */
	for( i=0; i<G.nbSommets; i++ )
		(*E)[i] = 1;
	
	/* On genenre combinaison par combinaison */
	/* Dans l'ordre decroissant et on test    */
	for(i=0; i<=G.nbSommets; i++)
	{
		/* Si on trouve un sous graphe triangule on s'arrete */
		if( combinaison(G, E, 0, i) )
			return 1;
	}
	
	/* On a rien trouve */
	return 0;
}


/**
 * @author ALENDA Régis - BOURGEOIS Jean-Louis
 * @brief Calcule un sous-graphe triangulé maximal d'un graphe quelconque.
 * Calcule un sous graphe triangulé maximal d'un graphe quelconque.
 * Renvoie une numérotation des sommets du sous-graphe triangulé. Les numéros non affectés (si le sous-graphe n'est pas le graphe tout entier) sont mis à -1.
 * @param G Un graphe.
 * @return Une numérotation du sous-graphe triangulé.
 */
Numerotation *LexBFS_SGTriangule( Graphe G )
{
      Etiquette E;
      Numerotation *N, *N2;
      int i, j, Max;
      int *marque;
      Maillon *I;

      start_clock();

      /* allocation mémoire */
      initEtiquette(&E, G.nbSommets);
      N = malloc(sizeof(Numerotation));
      N2 = malloc(sizeof(Numerotation));
      N->Numero = malloc( sizeof(int)*G.nbSommets );
      N->Sommet = malloc( sizeof(int)*G.nbSommets );
      N2->Numero = malloc( sizeof(int)*G.nbSommets );
      N2->Sommet = malloc( sizeof(int)*G.nbSommets );
      marque = (int *) malloc( sizeof(int) * G.nbSommets);

      /* initialisation */
      mettreEtiquetteAZero(&E);
      for(i=0;i<G.nbSommets;i++)
      {
            N->Numero[i] = -1;
            N->Sommet[i] = -1;
            N2->Numero[i] = -1;
            N2->Sommet[i] = -1;
            marque[i] = 0;
      }

      for(i=G.nbSommets-1; i>=0; i--)
      {

            /* on récupère un sommet d'étiquette maximale */
            Max = getMaxEtiquette(&E);

            /* si le sommet est quasi simplicial... */
            if(quasiSimplicial(Max, G, *N, marque))
            {
                  /* on ajoute ce sommet au graphe triangulé courant (on le numérote) */
                  N->Numero[Max] = i;
                  N->Sommet[i] = Max;

                  /* on incrémente l'étiquette de tous ses successeurs non numérotés */
                  FOREACH( I, G.Sommets[Max] )
                  {
                        if((N->Numero[I->elt]==-1) && (E.etiquette[I->elt] != -1))
                        {
                              incrementerEtiquette(I->elt, &E);
                        }
                  }
            }
            else
                  /* sinon on rejette le sommet */
                  E.etiquette[Max] = -1;
      }

      /* on crée la numérotation finale */
      j=0;
      for(i=0; i<G.nbSommets; i++)
      {
            if(N->Sommet[i] != -1)
            {
                  N2->Sommet[j] = N->Sommet[i];
                  N2->Numero[N->Sommet[i]] = j++;
            }
      }

      end_clock();

      free(N->Numero);
      free(N->Sommet);
      free(N);
      freeEtiquette(&E);
      free(marque);
      return N2;
}



/**
 * @author ALENDA Régis
 * @brief Teste si un sommet est quasi-simplicial dans une numérotation donnée.
 * Teste si un sommet est quasi-simplicial dans une numérotation donnée.
 * Le sommet ne doit pas être numéroté, et est considéré comme ayant un numéro plus petit que tous les autres.
 * Le tableau marque doit comporté autant d'éléments que de sommets dans le graphe, et doit être initialisé à zéro.
 * @param s Le sommet à tester.
 * @param G le graphe.
 * @param N La numérotation.
 * @param un tableau d'entier initialisé à zéro.
 * @return 1 si le sommet s est quasi simplicial dans G pour la numérotation N, 0 sinon.
 */
int quasiSimplicial( int s, Graphe G, Numerotation N, int *marque )
{
      Maillon *I;
      int result = 1, min = G.nbSommets;

      /* on cherche le voisin de s avec le plus petit numéro dans la numérotation */
      FOREACH(I, G.Sommets[s])
            min = ((N.Numero[I->elt] < min) && (N.Numero[I->elt] != -1)) ? N.Numero[I->elt] : min;

      if(min != G.nbSommets)
      {
            /* on vérifie que tous les voisins numérotés de s sont aussi des voisins de min */
            FOREACH(I, G.Sommets[N.Sommet[min]])
            {
                  if(N.Numero[I->elt] != -1)
                        marque[I->elt] = 1;
            }
            FOREACH(I, G.Sommets[s])
            {
                  if(marque[I->elt] == 0 && N.Numero[I->elt] != min && N.Numero[I->elt] != -1)
                  {
                        result = 0;
                        break;
                  }
            }
            FOREACH(I, G.Sommets[N.Sommet[min]])
            {
                  if(N.Numero[I->elt] != -1)
                        marque[I->elt] = 0;
            }
      }

      return result;
}

